1. Field of the Invention
The present invention relates to computer arithmetic, and more particularly to right-shifting an integer operand and rounding a fractional intermediate result towards or away from zero.
2. Description of Related Art
The Moving Picture Experts Group (MPEG) standard has emerged as the dominant standard for compressed digital video. The MPEG-1 standard specifies a compressed video bit-stream rate of approximately 1.5 megabits per second, and a compressed stereo audio bit-stream rate of approximately 250 kilobits per second. The second standard, MPEG-2, will specify compression rates for higher-bandwidth distribution media, and is in the process of being formalized. To meet the MPEG standard, video and audio compression and decompression products must rapidly process the various algorithms used to implement the MPEG standard.
Conventional right-shifters are used for fast division by 2.sup.N where N is an unsigned integer. Such shifters exploit the fact the operands represented in binary form are composed of bit positions that differ by powers of two. For instance, the bit positions of a four-bit unsigned binary operand typically represent 2.sup.3, 2.sup.2, 2.sup.1 and 2.sup.0. Therefore, division by 2.sup.N can be implemented by right-shifting the operand by N bit positions. When an unsigned operand is right-shifted the most significant bit (MSB) position is filled with a zero, and when a signed operand (in 2's complement form) is right-shifted the MSB position is filled with the MSB (or sign bit) of the operand. The right-shifter is usually not large enough to store the entire shifted operand. Consequently, operand bits are often shifted-out and discarded, and the result is not always numerically correct. Moreover, often no provision is made for a correctly rounded integer result. Various examples of signed operands applied to a conventional right-shifter and right-shifted by one and two bit positions are listed below in Tables 1 and 2.
TABLE 1 ______________________________________ SIGNED BINARY OPERANDS APPLIED TO CONVENTIONAL RIGHT-SHIFTER AND RIGHT-SHIFTED BY ONE BIT POSITION Binary Operand Binary Operand Right-Shifted by Right-Shifted by One Bit Position Binary One Bit Position - After Discarding Rounding Operand Actual Value Shifted-Out Bit Error (Decimal) (Decimal) (Decimal) (Decimal) ______________________________________ 0100 0010.0 0010 0 (decimal 4) (decimal 2) (decimal 2) (decimal 0) 0011 0001.1 0001 -0.1 (decimal 3) (decimal 1.5) (decimal 1) (decimal -0.5) 0010 0001.0 0001 0 (decimal 2) (decimal 1) (decimal 1) (decimal 0) 0001 0000.1 0000 -0.1 (decimal 1) (decimal 0.5) (decimal 0) (decimal -0.5) 1111 1111.1 1111 -0.1 (decimal -1) (decimal -0.5) (decimal -1) (decimal -0.5) 1110 1111.0 1111 0 (decimal -2) (decimal -1) (decimal -1) (decimal 0) 1101 1110.0 1110 -0.01 (decimal -3) (decimal -1.5) (decimal -2) (decimal -0.5) 1100 1110.0 1110 0 (decimal -4) (decimal -2) (decimal -2) (decimal 0) 1011 1101.1 1101 -0.1 (decimal -5) (decimal -2.5) (decimal -3) (decimal -0.5) ______________________________________
TABLE 2 ______________________________________ SIGNED BINARY OPERANDS APPLIED TO CONVENTIONAL RIGHT-SHIFTER AND RIGHT-SHIFTED BY TWO BIT POSITIONS Binary Operand Binary Operand Right-Shifted by Right-Shifted by Two Bit Positions Binary Two Bit Positions - After Discarding Rounding Operand Actual Value Shifted Out Bits Error (Decimal) (Decimal) (Decimal) (Decimal) ______________________________________ 0100 0001.00 0001 0 (decimal 4) (decimal 1) (decimal 1) (decimal 0) 0011 0000.11 0000 -0.11 (decimal 3) (decimal 0.75) (decimal 0) (decimal -0.75) 0010 0000.10 0000 -0.10 (decimal 2) (decimal 0.5) (decimal 0) (decimal -0.5) 0001 0000.01 0000 -0.01 (decimal 1) (decimal 0.25) (decimal 0) (decimal -0.25) 1111 1111.11 1111 -0.11 (decimal -1) (decimal -0.25) (decimal -1) (decimal -0.75) 1110 1111.10 1111 -0.10 (decimal -2) (decimal -0.5) (decimal -1) (decimal -0.5) 1101 1111.01 1111 -0.01 (decimal -3) (decimal -0.75) (decimal -1) (decimal -0.25) 1100 1111.00 1111 0 (decimal -4) (decimal -1) (decimal -1) (decimal 0) 1011 1110.11 1110 -0.11 (decimal -5) (decimal -1.25) (decimal -2) (decimal -0.75) ______________________________________
Tables 1 and 2 demonstrate that right-shifting an operand and discarding the shifted-out bit(s) leads to rounding towards minus infinity. That is, all non-integers are rounded towards the next smallest integer. For instance, right-shifting 0011 (decimal 3) by one bit position yields an actual value of 0001.1 (decimal 1.5), but discarding the shifted-out bit yields 0001 (decimal 1) with a rounding error of -0.1 (decimal -0.5). Right-shifting 1101 (decimal -3) by one bit position yields an actual value of 1110.1 (decimal -1.5), but discarding the shifted-out bit yields 1110 (decimal -2) with a rounding error of -0.1 (decimal -0.5). Right-shifting 0011 (decimal 3) by two bit positions yields an actual value of 0000.11 (decimal 0.75), but discarding the shifted-out bits yields 0000 (decimal 0) with a rounding error of -0.11 (decimal -0.75). Right-shifting 1101 (decimal -3) by two bit positions yields an actual value of 1111.01 (decimal -0.75), but discarding the shifted-out bits yields 1111 (decimal -1) with a rounding error of -0.01 (decimal -0.25).
In Tables 1 and 2, it is noted that the signed operands are represented in 2's complement form, and thus all bits except the sign bit have positive value. Furthermore, the shift length is not large enough to shift-out the sign bit. Therefore, since the shifted-out bits (or fractional bits) always have positive value, the rounding error is always in the direction of minus infinity.
Rounding towards minus infinity is generally undesirable since it introduces a bias towards minus infinity after repeated computations and rounding. The MPEG standard recognizes this problem. As a result, the MPEG standard defines two numerically unbiased rounding modes--"round towards zero" and "round away from zero". In round towards zero, numbers with a fractional component are rounded towards zero. That is, the integer component is left intact and the fractional component is truncated. In round away from zero, numbers with a fractional component are rounded to the closest integer, and numbers with a fractional component of a half-integer (the "tie case") are rounded away from zero. That is, when the number is positive and the fractional component is greater than or equal to one-half then the integer component is rounded up (towards plus infinity), when the number is positive and the fractional component is less than one-half then the integer component is left intact, when the number is negative and the absolute value of the fractional component is greater than or equal to one-half then the integer component is rounded up (towards minus infinity), and when the number is negative and the absolute value of the fractional component is less than one-half then the integer component is left intact.
Moreover, the MPEG standard defines "/" as integer division rounded towards zero, and "//" as integer division rounded away from zero. Various examples of integer division rounded towards zero and rounded away from zero are listed below in Table 3.
TABLE 3 ______________________________________ EXAMPLES OF INTEGER DIVISION ROUNDED TOWARDS ZERO AND ROUNDED AWAY FROM ZERO Integer Division With Integer Division With Rounding Towards Zero Rounding Away From Zero (X/Y) (X//Y) ______________________________________ 1/4 is rounded to 0 1//4 is rounded to 0 2/4 is rounded to 0 2//4 is rounded to 1 3/4 is rounded to 0 3//4 is rounded to 1 4/4 is rounded to 1 4//4 is rounded to 1 5/4 is rounded to 1 5//4 is rounded to 1 6/4 is rounded to 1 6//4 is rounded to 2 7/4 is rounded to 1 7//4 is rounded to 2 8/4 is rounded to 2 8//4 is rounded to 2 -1/4 is rounded to 0 -1//4 is rounded to 0 -2/4 is rounded to 0 -2//4 is rounded to -1 -3/4 is rounded to 0 -3//4 is rounded to -1 -4/4 is rounded to -1 -4//4 is rounded to -1 -5/4 is rounded to -1 -5//4 is rounded to -1 -6/4 is rounded to -1 -6//4 is rounded to -2 -7/4 is rounded to -1 -7//4 is rounded to -2 -8/4 is rounded to -2 -8//4 is rounded to -2 ______________________________________
Therefore, in calculation intensive applications such as MPEG motion processing, it is highly desirable to round fractional intermediate results towards or away from zero in a rapid and efficient manner.